package medium;

import java.util.Arrays;

/**
 * @author shizhun
 * @description:
 * @date 2025/9/19 11:36
 * @see DeviceEntity
 */
public class t31 {
    public static void main(String[] args) {
        Arrays.stream(new t31().nextPermutation(new int[]{2,2,7,5,4,3,2,2,1})).forEach(System.out::print);
    }

    public int[] nextPermutation(int[] nums) {
        // 找到最后一个递增的子列
        // 例如 123764651：最后一个递增子列是46
        // 找到4后面最后一个大于4的数，交换位置 找到5
        // 在将4后面的数组进行翻转得到123765146为最终答案
        // 如果没有递增子列，则翻转整个数组
        findLastArr(nums, nums.length - 2, nums.length - 1);
        return nums;
    }

    /**
     * @param nums  输入的数组
     * @param index 指针
     */
    public void findLastArr(int[] nums, int index, int end) {

        if (-1 == index) {
            return;
        }
        // 4,2,0,2,3,2,0 |4 2 0 3 0 2 2
        for (int i = index; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                for (int j = i + 1; j <= end; j++) {
                    if (nums[j] > nums[i] && j != end) {
                        continue;
                    } else {
                        if (nums[j]>nums[i]){
                            swap(nums, i, j);
                            reverse(nums, i + 1);
                            return;
                        }else {
                            swap(nums, i, j - 1);
                            reverse(nums, i + 1);
                            return;
                        }
                    }
                }
                swap(nums, i, i + 1);
                reverse(nums, i + 1);
                return;
            }
        }
        reverse(nums, 0);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

}
